package 回溯;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;
import com.google.common.collect.Lists;
import org.apache.commons.lang3.StringUtils;
import org.apache.commons.lang3.math.NumberUtils;

import java.net.URLDecoder;
import java.util.*;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 最大兼容性评分和1947.java
 * @createTime 2023年04月07日 15:54:00
 */
public class 最大兼容性评分和1947 {

	private static boolean a= false;
	public static void main(String[] args) {
		ArrayList<Integer> integers = Lists.newArrayList(1, 2, 34, 5, 3);
		List<List<Integer>> partition = Lists.partition(integers, 2);
		System.out.println(partition);
	}
	int result = 0;

	public int maxCompatibilitySum(int[][] students, int[][] mentors) {
		int s = students.length;
		boolean[] used = new boolean[s];
		int[][] score = new int[s][s];
		//先计算不同情况的分数
		for (int i = 0; i < s; i++) {
			for (int j = 0; j < s; j++) {
				score[i][j] = calScore(students[i], mentors[j]);
			}
		}
		//计算分数最大值
		backTrace(score, s, used, 0, 0);
		return result;
	}

	public int calScore(int[] student, int[] mentor) {
		int score = 0;
		for (int i = 0; i < student.length; i++) {
			if (student[i] == mentor[i]) {
				score += 1;
			}
		}
		return score;
	}

	public void backTrace(int[][] scores, int length, boolean[] used, int sIndex, int total) {
		//长度是学生的个数
		if (length == sIndex) {
			result = Math.max(result, total);
			return;
		}
		//这里长度是老师的个数，因为学生和老师数量一样，所以都取得length，计算第sIndex个学生，和不同老师的匹配情况下的得分
		for (int i = 0; i < length; i++) {
			if (used[i]) {
				continue;
			}
			used[i] = true;
			//计算第sIndex个学生和第i个老师的组合情况
			backTrace(scores, length, used, sIndex + 1, total + scores[sIndex][i]);
			used[i] = false;
		}
	}
}
